algo / LeetCode / 系列合集 16 分钟读完 (大约2440个字) 0次访问

[LeetCode]买卖股票合集

简单整理一下LeetCode上买卖股票系列题目. 包含买卖股票的最佳时机、买卖股票的最佳时机 II、买卖股票的最佳时机 III、买卖股票的最佳时机 IV、最佳买卖股票时机含冷冻期和买卖股票的最佳时机含手续费共六题.

买卖股票的最佳时机

题目描述

给出数组price, 其中price[i]表示第i天股票的价格. 只能选择某一天买入然后之后的某一天卖出, 求最大利润.

思路

  • 贪心. 如果在第i天卖出, 那么一定希望买入的时候价格最低, 因此使用维护一个前缀最小值即可.
  • 状态机动态规划
    • 状态机关心的时当前处于何种状态, 以及所有可能的状态转移和条件
    • 动态规划
      • 状态定义
        1. f[i][0][0]: 表示第i天没持有股票, 且没完成一次交易的最大利润(一定为0).
        2. f[i][1][0]: 表示第i天持有股票, 且没完成一次交易的最大利润.
        3. f[i][0][1]: 表示第i天没持有股票, 且完成一次交易的最大利润.
        4. f[i][1][1]: 表示第i天持有股票, 且完成一次交易的最大利润.
      • 状态转移
        1. $f[i][0][0] = f[i - 1][0][0] = 0$
        2. $f[i][1][0] = max(f[i - 1][1][0], -price[i])$, 表示要么是第i - 1天持有, 要么是第i天买入.
        3. $f[i][0][1] = max(f[i - 1][0][1], f[i - 1][1][0] + price[i])$, 表示要么是第i - 1天完成一次交易, 要么是第i天卖出后完成了一次交易.
        4. $f[i][1][1] = max(f[i - 1][1][1], f[i - 1][0][1] - price[i])$, 表示要么是第i - 1天持有, 要么是第i天买入.
    • 使用三维的原因是必须保证只能完成一次交易, 因此需要对状态进行拆分.
    • 状态的表示是持有股票或不持有股票, 而买入卖出是动作, 是状态转移的条件.
    • 状态初始化中, 由于第一天无法完成一次交易, 因此$f[1][0][1]=f[1][1][1]=-INF$.
    • 由于$f[i][1][1]$无法转移到其他任何状态, 而且其也不会是答案, 因此其为无效状态, 无需计算.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 
  贪心思路, 记录前缀最小值即可.
    时间复杂度O(N)
    空间复杂度O(1)
*/
class Solution {
public:
    int maxProfit(vector<int>& p) {
        // ans至少为0, 即可以不买不卖
        int ans = 0, mn = p[0];
        for (int i = 1; i < (int)p.size(); i ++ ){
            ans = max(ans, p[i] - mn);
            mn = min(mn, p[i]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 状态机动态规划
const int N = 1e5 + 5;
class Solution {
public:
    int f[N][2][2];
    int maxProfit(vector<int>& p) {
        int n = p.size();
        f[1][0][1] = f[1][1][1] = -1e9;
        f[1][1][0] = -p[0];
        for (int i = 2; i <= n; i ++ ) {
            f[i][0][0] = f[i - 1][0][0];
            f[i][1][0] = max(f[i - 1][1][0], -p[i - 1]);
            f[i][0][1] = max(f[i - 1][0][1], f[i - 1][1][0] + p[i - 1]);
        }
        return max(f[n][0][1], f[n][0][0]);
    }
};

复杂度分析(状态机动态规划)

  • 时间复杂度$O(N)$
  • 空间复杂度$O(N)$

买卖股票的最佳时机 II

题目描述

基本题意与第一题相同, 只是多了个条件: 可以完成任意交易.

思路

  • 本题无需关注交易次数, 只需关注在每个时间点所处的状态以及所有可能的转移及条件, 因此简单修改第一题状态机动态规划做法即可.
  • 状态机动态规划
    • 状态定义:
      1. f[i][0]: 表示第i天没持有股票时候的最大收益
      2. f[i][1]: 表示第i天持有股票时候的最大收益
    • 状态转移:
      1. $f[i][0] = max(f[i - 1][0], f[i - 1][1] + price[i])$, 表示第i天不持有可以从第i - 1天不持有或者第i - 1天持有但第i天卖掉转移而来.
      2. $f[i][1] = max(f[i - 1][1], f[i - 1][0] - price[i])$, 表示第i天持有可以从第i - 1天持有或者第i - 1天不持有但第i天买入转移而来.
  • 最终答案: f[n][0]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& p) {
        int n = p.size();
        vector<vector<int>> f(n, vector<int>(2, 0));
        f[0][0] = 0, f[0][1] = -p[0];
        for (int i = 1; i < n; i ++ ){
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + p[i]);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - p[i]);
        }
        return f[n - 1][0];
    }
};

复杂度分析

  • 时间复杂度$O(N)$
  • 空间复杂度$O(N)$

买卖股票的最佳时机 III

题目描述

基本题意与第一题相同, 只是多了个条件: 最多完成两笔交易.

思路

  • 第一题解法中使用三维状态来标记完成交易的次数, 本题只是第一题的简单扩展, 在第一题基础上稍加修改即可.
  • 状态机动态规划
    • 状态定义:
      1. $f[i][0][0]$: 表示第i天不持有股票, 且完成0笔交易时的最大收益(一定为0, 无效状态)
      2. $f[i][1][0]$: 表示第i天持有股票, 且完成0笔交易时的最大收益
      3. $f[i][0][1]$: 表示第i天不持有股票, 且完成1笔交易时的最大收益
      4. $f[i][0][2]$: 表示第i天不持有股票, 且完成2笔交易时的最大收益
      5. $f[i][1][1]$: 表示第i天持有股票, 且完成1笔交易时的最大收益
      6. $f[i][1][2]$: 表示第i天持有股票, 且完成2笔交易时的最大收益(无效状态)
    • 状态转移:
      1. $f[i][1][0] = max(f[i - 1][1][0], f[i - 1][0][0] - p[i])$, 表示第i天持有可以从第i - 1天持有或者第i - 1天不持有但第i天买入转移而来.
      2. $f[i][0][1] = max(f[i - 1][0][1], f[i - 1][1][0] + p[i])$, 转移同上, 要么前一天同状态转移过来, 要么前一天某状态通过买入/卖出转移过来.
      3. $f[i][0][2] = max(f[i - 1][0][2], f[i - 1][1][1] + p[i])$
      4. $f[i][1][1] = max(f[i - 1][1][1], f[i - 1][0][1] - p[i])$
    • 由于第一天无法完成交易, 因此需要初始化第一天的某些状态为非法状态.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N = 1e5 + 5;
class Solution {
public:
    int f[N][2][3];
    int maxProfit(vector<int>& p) {
        int n = p.size();
        // 初始化
        // 第一天持有股票
        f[1][1][0] = -p[0];
        // 第一天无法完成交易
        f[1][0][1] = f[1][0][2] = f[1][1][1] = f[1][1][2] = -1e9;
        for (int i = 2; i <= n; i ++ ) {
            int cur = p[i - 1];
            // 第i天有股票, 交易了0次
            f[i][1][0] = max(f[i - 1][1][0], - cur);
            // 第i天无股票, 交易了1次
            f[i][0][1] = max(f[i - 1][0][1], f[i - 1][1][0] + cur);
            // 第i天无股票, 交易了2次
            f[i][0][2] = max(f[i - 1][0][2], f[i - 1][1][1] + cur);
            // 第i天有股票, 交易了1次
            f[i][1][1] = max(f[i - 1][1][1], f[i - 1][0][1] - cur);
        }
        return max({f[n][0][0], f[n][0][1], f[n][0][2]});
    }
};

复杂度分析

  • 时间复杂度$O(N)$
  • 空间复杂度$O(N)$

买卖股票的最佳时机 IV

题目描述

基本题意与第一题相同, 只是多了个条件: 最多完成k笔交易.

思路

  • 第一题状态机动态规划解法与第三题的推广版本, 完全一致的思路, 照抄即可.
  • 状态机动态规划
    • 状态定义:
      1. $f[i][0][j]$: 表示第i天不持有股票, 且完成j笔交易时的最大收益
      2. $f[i][1][j]$: 表示第i天持有股票, 且完成j笔交易时的最大收益
    • 状态转移:
      1. $f[i][0][j] = max(f[i - 1][0][j], f[i - 1][1][j - 1] + p[i])$
      2. $f[i][1][j] = max(f[i - 1][1][j], f[i - 1][0][j] - p[i])$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 1010, K = 110;
class Solution {
public:
    int f[N][2][K];
    int maxProfit(int k, vector<int>& p) {
        memset(f, -0x3f, sizeof(f));
        int n = p.size();
        for (int i = 0; i <= n; i ++ )
            f[n][0][0] = 0;
        for (int i = 1; i <= n; i ++ ) {
            int cur = p[i - 1];
            f[i][1][0] = max(f[i - 1][1][0], -cur);
            for (int j = 1; j <= k; j ++ ) {
                f[i][0][j] = max(f[i - 1][0][j], f[i - 1][1][j - 1] + cur);
                f[i][1][j] = max(f[i - 1][1][j], f[i - 1][0][j] - cur);
            }
        }
        int ans = 0;
        for (int i = 1; i <= k; i ++ )
            ans = max(ans, f[n][0][i]);
        return ans;
    }
};

复杂度分析

  • 时间复杂度$O(N * K)$
  • 空间复杂度$O(N * K)$

最佳买卖股票时机含冷冻期

题目描述

基本题意与第一题相同, 只是多了条件: 可以买卖任意次, 但卖出股票后，无法在第二天买入股票 (即冷冻期为 1 天)。

思路

  • 基本为第二题的扩展. 考虑如何将冷冻期为 1 天用状态表达出来即可.
  • 状态机动态规划
    • 状态定义:
      1. $f[i][0]$: 表示第i天不持有股票, 且无冷冻期, 时候的最大收益.
      2. $f[i][1]$: 表示第i天不持有股票, 且在冷冻期(第i - 1天卖出), 时候的最大收益.
      3. $f[i][2]$: 表示第i天持有股票时候的最大收益
    • 状态转移:
      1. $f[i][0] = max(f[i - 1][0], f[i - 1][1])$
      2. $f[i][1] = f[i - 1][2] + p[i]$
      3. $f[i][2] = max(f[i - 1][2], f[i - 1][0] - p[i])$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& p) {
        int n = p.size();
        vector<vector<int>> f(n + 1, vector<int>(3, 0));
        // 初始化:
        f[1][1] = -1e9;
        f[1][2] = -p[0];
        for (int i = 2; i <= n; i ++ ) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][2] + p[i - 1];
            f[i][2] = max(f[i - 1][2], f[i - 1][0] - p[i - 1]);
        } 
        return max(f[n][0], f[n][1]);
    }
};

复杂度分析

  • 时间复杂度$O(N)$
  • 空间复杂度$O(N)$

买卖股票的最佳时机含手续费

题目描述

基本题意与第一题相同, 只是多了条件: 可以买卖任意次, 且一次买入卖出需要支付手续费。

思路

  • 第二题的简单扩展. 卖出阶段支付手续费即可.
  • 状态机动态规划
    • 状态定义:
      1. $f[i][0]$: 表示第i天不持有股票时候的最大收益.
      2. $f[i][1]$: 表示第i天持有股票时候的最大收益.
    • 状态转移:
      1. $f[i][0] = max(f[i - 1][0], f[i - 1][1] + p[i] - fee)$
      2. $f[i][1] = max(f[i - 1][1], f[i - 1][0] - p[i])$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N = 1e5 + 5;
class Solution {
public:
    int f[N][2];
    int maxProfit(vector<int>& p, int fee) {
        int n = p.size();
        f[1][1] = -p[0];
        for (int i = 2; i <= n; i ++ ) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + p[i - 1] - fee);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - p[i - 1]);
        }

        return f[n][0];
    }
};

复杂度分析

  • 时间复杂度$O(N)$
  • 空间复杂度$O(N)$

参考资料

欢迎讨论指正

[LeetCode]买卖股票合集

https://csjsss.github.io/2021/11/23/algo/LeetCode/系列合集/[LeetCode]买卖股票合集/

作者

Jsss

发布于

2021-11-23

更新于

2021-12-27

许可协议

 

喜欢这篇文章？打赏一下作者吧

评论

最新文章

标签

0-1BFS1
AcWing Cup1
BFS2
DFS1
LeetCode3
Linux1
RAII1
STL1
Spdlog1
cpp4
enable_shared_from_this1
二分1
二分搜索3
优先队列1
八股文1
共享主存1
前缀和5
动态规划14
区间最值1
匿名管道1
单调队列1
双指针1
同步原语1
周赛4
命名管道1
哈希表1
字符串分割1
工具软件1
差分1
平衡树1
并查集1
思维2
拓扑排序1
数据结构2
无锁队列1
最短路1
枚举8
树状数组2
模拟14
深度优先搜索1
状态压缩1
状态压缩动态规划1
状态机2
生产者-消费者1
语言基础2
贪心8
资源管理类2
进程通信1
连通性1
递推1
链表1

订阅更新

follow.it

×